"""
对于文件的输入规范：
如果是变量 需要全部大写
不为变量 就是终结符(空串符号也是终结符)
不同产生式间 用|分割
两个变量/非终结符间使用空格隔开（这样就可以使用多个字符描述一个变量/终结符，eg：用none描述空串）
空串使用none代替

二型文法转格雷巴赫范式
二型文法 对于任意产生式 α->β α是一个单一的变量(非终结符) β是终结符和变量的随意组合 但是其长度大于α
算法的流程为：
CFG -> 化简的CFG -> GNF
化简CFG：
1.去除无用符号
2.去除空符号
3.去除单一产生式
"""

import collections


def showProductions(P: collections.defaultdict(list)):
    print('________________showProductions_______________')
    for left, rights in P.items():
        # print(left, 'right num:', len(rights))

        production = left + ' -> '
        for i, right in enumerate(rights):
            production += ''.join([s + ' ' for s, attr in right])
            if i < len(rights)-1:
                production += '| '
            # print(''.join([s + ' ' for s, attr in right]))

        print(production, '\n')


def readProductions(path):
    P = collections.defaultdict(list)
    V = set()
    T = set()
    with open(path, 'r') as f:
        for line in f.readlines():
            # line = line.strip('\n').split()
            line = line.strip('\n')
            left, rights = line.split('->')
            left = left.strip()
            V.add(left)
            # print(left, rights)
            for right in rights.split('|'):
                # P[left].append(right.split())
                right_list = []
                for symbol in right.split():
                    if symbol.isupper():
                        right_list.append((symbol, 'Variable'))
                        V.add(symbol)
                    else:
                        right_list.append((symbol, 'Terminal'))
                        T.add(symbol)
                P[left].append(right_list)
    # print(P)
    # print(V)
    # print(T)
    print('读取产生式:')
    showProductions(P)
    return V, T, P


def allInSet(right, s):
    for symbol, attr in right:
        if symbol not in s:
            return False
    return True


"""
去除无用符号：
包括两种情形， 分别对应如下两个方法， 且必须先使用方法1， 再使用方法2
1. 由终结符出发 往回推 看看哪些符号能最终生成句子  这样去除的是哪些一旦出现在句型中就永远不会消失的变量
2. 由开始符出发 看看都能到达哪些变量， 达到不了的变量 说明其根本不可能出现在句型中
"""


def removeUselessSymbol1(V, T, P, S=None):
    oldV = set()
    newV = set()

    for left, rights in P.items():
        for right in rights:
            if allInSet(right, T):
                newV.add(left)

    while oldV != newV:
        oldV = newV

        tmp = set()
        for left, rights in P.items():
            for right in rights:
                if allInSet(right, T | oldV):
                    tmp.add(left)
        newV = oldV | tmp

    resV = newV
    resP = collections.defaultdict(list)
    for left, rights in P.items():
        for right in rights:
            if allInSet(right, T | resV):
                resP[left].append(right)

    # print(resV)
    # print(resP)
    return resV, T, resP, S


def removeUselessSymbol2(V, T, P, S=None):
    oldV, oldT, newV, newT = set(), set(), set(), set()
    newV.add(S)
    for right in P[S]:
        for symbol, attr in right:
            if attr == 'Variable':
                newV.add(symbol)
            if attr == 'Terminal':
                newT.add(symbol)

    while oldV != newV or oldT != newT:
        oldV, oldT = newV, newT  # 标记为旧的
        tmpV, tmpT = set(), set()
        for var in oldV:
            if var in P:
                for right in P[var]:
                    for symbol, attr in right:
                        if attr == 'Variable':
                            tmpV.add(symbol)
                        if attr == 'Terminal':
                            tmpT.add(symbol)
        newV = oldV | tmpV
        newT = oldT | tmpT

    resV = newV
    resT = newT
    resP = collections.defaultdict(list)
    for var in resV:
        for right in P[var]:
            if allInSet(right, resV | resT):
                resP[var].append(right)

    # print(resV)
    # print(resT)
    # print(resP)
    print('去除无用符号结果：')
    showProductions(resP)
    return resV, resT, resP, S


def removeUselessSymbol(V, T, P, S=None):
    return removeUselessSymbol2(*removeUselessSymbol1(V, T, P, S))


"""
去除空串符号
首先要找所有的可空变量集U 即找到所有可能直接产生空集的变量 eg: S->012B|2A A->23B|B B->1|none 那么A，B变量都可以推导到none
去除产生式中的可空变量
如果产生新的产生式就加入
如果去掉可空变量后变为空 就不需要这个产生式了
"""


def findU(V, T, P, S=None):
    oldU, newU = set(), set()
    for left, rights in P.items():
        for right in rights:
            for symbol, attr in right:
                if symbol == 'none':
                    newU.add(left)

    while newU != oldU:
        oldU = newU
        tmpU = set()
        for left, rights in P.items():
            for right in rights:
                if allInSet(right, oldU | {'none'}):
                    tmpU.add(left)
                    break

        newU = oldU | tmpU

    resU = newU
    return resU


# def removeNone(V, T, P, S=None):
#     U = findU(V, T, P, S)
#     resP = collections.defaultdict(list)
#
#     for left, rights in P.items():
#         for right in rights:
#             if ('none', 'Terminal') in right:  # 将直接导向none的产生式不加入结果（去除）
#                 continue
#
#             withoutNone = []
#             for symbol, attr in right:
#                 if symbol not in U:
#                     withoutNone.append((symbol, attr))
#             """
#             这里将所有产生式中的可空变量移除（不加入产生式）
#             其实这里有一个bug: S->aABCD 假如ABCD都是可空变量
#             ABCD产生式中的空产生式都移除了，如果按照这样的处理方式S 那么只有 S->a 和 S->aABCD
#             类似于单独某个变量变为空的情况就没有了 S->aABC S->aBCD 以及组合的情况 S->aBC S->aAD之类的
#             """
#
#             if right == withoutNone:
#                 # 没有能导致None的变量 那就直接加入
#                 resP[left].append(right)
#             elif len(withoutNone) == 0:
#                 # 全都是导致None的变量 这个产生式就不用了
#                 continue
#             else:
#                 # 部分是导致None的变量 那么原式子要加入 新式子也要加入
#                 resP[left].append(right)
#                 if withoutNone not in resP[left]:
#                     resP[left].append(withoutNone)
#
#     # print(resP)
#     return V, T, resP, S

def removeNone(V, T, P, S=None):
    U = findU(V, T, P, S)
    resP = collections.defaultdict(list)

    for left, rights in P.items():
        for right in rights:
            if ('none', 'Terminal') in right:  # 将直接导向none的产生式不加入结果（去除）
                continue

            withoutNones = []
            withoutNone = []

            def DFS(index):
                if index == len(right):
                    withoutNones.append(withoutNone[:])
                    return

                if right[index][0] in U:
                    withoutNone.append(right[index])
                    DFS(index+1)
                    withoutNone.pop()

                    DFS(index+1)
                else:
                    withoutNone.append(right[index])
                    DFS(index+1)
                    withoutNone.pop()

            DFS(0)
            # print(withoutNones)
            """
            通过DFS可以生成可空变量的任意组合情况
            """

            for withoutNone in withoutNones:
                if len(withoutNone) == 0:
                    continue
                else:
                    if withoutNone not in resP[left]:
                        resP[left].append(withoutNone)
            if right not in resP[left]:
                resP[left].append(right)

    # print(resP)
    print('去除空产生式结果：')
    showProductions(resP)
    return V, T, resP, S


"""
去除单一产生式 就是说遇到A->B(两边都是单个变量)的产生式 都要去除
去除A->B的方式是去推导B 如果B的产生式B->α都不是单一产生式就加入新的产生式A->α
"""


def removeUnit(V, T, P, S=None):
    resP = collections.defaultdict(list)

    def findRightsWithoutUnit(left, recursion_path):
        # 直到一个变量没有单一产生式为止
        tmp = []
        for right in P[left]:
            if not (len(right) == 1 and right[0][1] == 'Variable'):  # 不是单一产生式
                tmp.append(right)
            else:  # 是单一产生式就把其变量对应的产生式吸纳到当前的产生式中
                if right[0][0] not in recursion_path:
                    recursion_path.add(right[0][0])
                    tmp += findRightsWithoutUnit(right[0][0], recursion_path)

        return tmp

    for left, rights in P.items():
        for right in rights:
            if not (len(right) == 1 and right[0][1] == 'Variable'):  # 不是单一产生式
                if right not in resP[left]:  # 因为在下面的递归过程中可能会提前将产生式移入结果中， 避免重复
                    resP[left].append(right)
            else:
                # 获得是单一产生式的rights
                recursion_path = {right[0][0]}
                for r in findRightsWithoutUnit(right[0][0], recursion_path):
                    if r not in resP[left]:
                        resP[left].append(r)
                # resP[left] += findRightsWithoutUnit(right[0][0])

    # print(resP)
    print('去除单一产生式结果：')
    showProductions(resP)
    return V, T, resP, S


def reduceGrammar(Path, S='S'):
    return removeUselessSymbol(*removeUnit(*removeNone(*removeUselessSymbol(*readProductions(Path), S=S))))


if __name__ == '__main__':
    # path = 'D:\\p.txt'
    path = 'p2.txt'
    # V, T, P, S = removeUselessSymbol1(*readProductions(path))
    V, T, P, S = reduceGrammar(path, S='S')
    # print(P)
    print('最终结果：')
    showProductions(P)
